//  homedepot.c
//	Test program for the assignment 1.
//	Test the implementation of synchronization mechanisms
//  of Lock and Condition.
//
//	OceanMaster

#include "copyright.h"
#include "system.h"
#include "synch.h"
#include <stdlib.h>

//Predefine
#define R_MAX 2147483647	//R_MAX denotes the biggest possible number returned of rand(); RAND_MAX is somehow out of time.
#define TestCaseNum 9		//Total number of pre defined test cases
//Pre Defined Test Cases
//Name
char * TestCaseName[TestCaseNum] = {
										"TestCase1, Customer always take the shortest line, but no 2 customers ever choose the same",
										"TestCase2, Customer don't leave until given receipt. Clerk doesn't serve another until one customer left", 
										"TestCase3, Customer hand each item to clerk only after the clerk has scanned previous one and ready", 
										"TestCase4, Clerks go on break when they have no one waiting in their line", 
										"TestCase5, Manager get clerks off their break when lines get too long", 
										"TestCase6, Total sales never suffer from a race condition, Manager only talk to one Cash Reg at a time", 
										"TestCase7, Stock Boy help one customer at a time;", 
										"TestCase8, Only one StockBoy enters the stock room at a time", 
										"Minimal Requirement"	};
//Value				ClerkNum	StockBoyNum		CustomerNum
int TestCase[][3] = {{	0,			0,				10		},				//TestCase1 
					{	1,			0,				3		},				//TestCase2 
					{	1,			0,				1		},				//TestCase3	
					{	2,			0,				1		},				//TestCase4
					{	5,			0,				5		},				//TestCase5
					{	5,			0,				2000	},				//TestCase6	
					{	1,			1,				5		},				//TestCase7 
					{	0,			5,				0		},				//TestCase8 
					{	3,			3,				20		}};				//Minimal Requirement

//=======================Structs==========================
//-------------------Customer Struct----------------------
//	Struct for Customer
//	To store personal data
//--------------------------------------------------------
//---------------------Clerk Struct-----------------------
//	Struct for Clerk
//	To store personal data
//--------------------------------------------------------
//---------------------CashReg Struct---------------------
//	Struct for CashReg
//	To store personal data
//--------------------------------------------------------
//---------------------StockBoy Struct--------------------
//	Struct for Customer
//	To store personal data
//--------------------------------------------------------
//---------------------Manager Struct---------------------
//	Struct for Manager
//	To store personal data
//--------------------------------------------------------
//========================================================

//Function Define
int GenRandom(int limit);
void CustomerBehavior(int);		
void ClerkBehavior(int);
void ManagerBehavior(int);
void CashRegisterBehavior(int);
void StockBoyBehavior(int);
//Function Define End

//Constant Varible Define

bool ProgramRun = true;		//Is program running?

double * Prices;			//prices of corresponding item
int * ItemAmount;			//Amount of each item, REMEMBER to INIT!! originally 3
int * ItemRestockPrediction;//Amount of each item that stockboy is restocking and will soon be restocked

int ClerkNum;				//total # of clerks;
int CRNum;					//total # of cash registers
int CustomerNum;			//total # of Customer
int StockBoyNum;			//total # of StockBoy
int ManagerNum = 1;			//total # of Manager
int ItemNum = 10;			//total # of Item
int AisleNum = 5;			//total # of Aisle
int testCases[TestCaseNum][5];	//TestCases

//Test Case Tricks
//These Varibles is used to create specific scenario for test cases
int ReturnChance = 20;		//The chance if a customer to be return customer
int LostChance = 25;		//The chance a customer fails to find an item
int OriginItemAmount = 3;	//Origin Amount of each Item
int	MinBoughtEach = 1;		//Min number of items a customer can buy
int MaxBoughtEach = 10;		//Max number of items a customer can buy is [MinBoughtEach+MaxBoughtEach-1]
bool * BornLazy;			//If a clerk will go to rest as soon as he is created?
int PriceFactor = 100;		//The Factor that affects randomly generated prices
double MinPrice = 0.0;		//The Mininum price can be generated
bool ManagerTrackLine = true;	//Does Manager keep track of Line himself
bool CustomerBusyWaiting = false; //This is a trick to let customer keeps searching for stockboy.This value is always false in normal simulation

//Constant Verible End
//Shared Varible & Synchronization Define
bool * AisleNeedRestock;	//record if an aisle need to be restocked
double TotalSales=0.0;		//record the total sales amount.

Lock * OpLock1;				//StartLine Exclusion
Lock * OpLock2;				//StockBoy Break Exclusion
Lock * OpLock3;				//Clerk Break Exclusion
Lock * OpLock4;				//Leaving Customer Exclusion
Lock * OpLock5;				//For StockRoom Condition Check	

Condition * StartLine;		//the start line

bool ServiceButtonOn=false;	//If somebody pressed service button?
bool ClerkCall=false;		//If somebody ask for more clerk?
int ClerkCallId = -1;		//The Clerk who asked manager to wake another clerk

Condition * ClerkOnBreak;	//The Condition that clerks on break wait on
Condition * StockBoyOnBreak;//The Condition that stockboys on break wait on

Lock * CheckQueue;			//Acquire this lock before check Line Lengths
int * QueueLength;			//Lengths of paying Lines
Condition * * Queue;		//Paying Lines
bool * ClerkOnWork;			//If a Clerk is ready for customer?

Lock * * TableLock;			//Acquire this Lock before handle items on table
Condition * * Table;		//The Cashier Table State Condition
int * TableArea;			//Place to put items
double * CashArea;			//Place to put money

Lock * * ScreenLock;		//Acquire this Lock before interact with cash register machine
Condition * * Screen;		//The cash register machine screen State Condition
double * data;				//The data is the place to exchange information with cash register
double * MoneyCollected;	//The money each cash register earned before manager empty it
double * TotalMoneyCollected;//The money each cash register ever earned
double * MoneyLacked;		//The money a cash register lacks to pay a return customer
Condition * * LackMoney;	//If a cash register lacks money to pay return customer, he waits for Manager here


Lock * StockRoomLock;		//The Lock on StockRoom
Condition * StockRoomCV;	//The Condition on which Stock Boy wait for room
int StockBoyInRoom = -1;	//Id of StockBoy currently in Stock Room

Lock * * AisleLock;			//Acquire this Lock before access any item on an aisle
int * StockBoyStatus;		//Each StockBoy's status.If he is in an aisle, status is the aisle number or aisle+AisleNum; Otherwise,  -1
int * AisleHelpLineLength;	//The number of customer waiting for help on each aisle
Lock * * ServiceStateLock;	//The Lock to protect help state between a stock boy and a customer
Condition * * ServiceStateCV;//The State Condition when a stock boy is helping a customer
int * Booklet;				//The booklet used by Customer and StockBoy to exchange information

Lock * ServiceButtonLock;	//The Lock to protect service button
Lock * ClerkCallLock;		//The Lock to protect clerk call flag

Lock * StockBoyStatusLock;	//The Lock to protect Stock Boy Status
Lock * * AisleHelpLock;		//The Lock to protect AisleHelp related monitor varibles
Condition * * AisleHelpCV;	//The Condition a customer waits on before a stock boy comes to serve him

int CustomerLeaving=0;		//Total number of customers that finished shopping and left

Condition * * WaitForRestockCV;//Customers waiting for item to be restocked. It is protected by AisleLock

bool * DidSomething;
//Shared Varible & Synchronizations End


//Main function for Home Depot Simulation
//========================================================
void
HomeDepotRun()	//main function for Home Depot
{
	printf("============================================\n");
	printf("         Home Depot Store Simulation        \n\n");
	printf("          part2 of project1,CSCI402         \n");
	printf("                  Group#11                  \n");
	printf("============================================\n\n");
	
	//---------------------------
	//      CONFIG   Phase1
	//---------------------------
	
	// Phase 1 Config mainly config basic varibles that initialization relies on
	
	//Config part can't be a loop, or the result won't be repeatable!!
	
	printf("=========== Home Depot Configure ===========\n");				//Print Configure Interface

	printf("ID  Clk  Stk  Customer  Description\n");
	for(int i = 0; i < TestCaseNum; i++)									//List Pre-defined Test Cases
	{
		printf("%2d  %3d  %3d  %8d  %-s\n",i,TestCase[i][0],TestCase[i][1],TestCase[i][2], TestCaseName[i]);
	}
	printf("%2d    ?    ?         ?  User Configuration Input\n",TestCaseNum);

	printf("Please input the Testcase ID:");								//Ask User to choose a Test case or input user configured data

	int TestCaseId;
	scanf("%d",&TestCaseId);												//read in user selection
	
	if(TestCaseId<0 || TestCaseId>TestCaseNum)								//Quit on invalid Selection
	{
		printf("Invalid TestCase Id ,program terminate.\n");
		return;
	}
	else if (TestCaseId == TestCaseNum)										//Read in user input if user select "User Configuration"
	{
		printf("User Config TestCase:\n");
		printf("Please Input Clerk Number:");
		scanf("%d",&ClerkNum);
		CRNum=ClerkNum;
		printf("Please Input Customer Number:");
		scanf("%d",&CustomerNum);
		printf("Please Input StockBoy Number:");
		scanf("%d",&StockBoyNum);
	}
	else																	//Else, configure as each test case needed
	{
		printf("TestCase [%d] selected\n",TestCaseId);
		
		ClerkNum = TestCase[TestCaseId][0];									//Config ClerkNum,StockBoyNum and CustomerNum
		CRNum = ClerkNum;
		StockBoyNum = TestCase[TestCaseId][1];
		CustomerNum = TestCase[TestCaseId][2];
	
		switch(TestCaseId)													//Do special Config for each Test Case
		{
			case 0:	//TestCase1
					CRNum = 3;
					ClerkNum = 0;				//set no clerk so unrelated information won't be printed
					ManagerNum = 0;				//set no manager so unrelated information won't be printed
					LostChance = 0;				//impossible to fail to find some item
					ReturnChance = 0;			//impossible to be return customer
					OriginItemAmount = 1000;	//items won't be sold out
					break;
			case 1:	//TestCase2
					ManagerNum = 0;	
					LostChance = 0;
					ReturnChance = 0;
					OriginItemAmount = 1000;
					break;
			case 2:	//TestCase3
					ManagerNum = 0;	
					LostChance = 0;
					ReturnChance = 0;
					OriginItemAmount = 1000;
					MinBoughtEach = 5;			//each customer buy at least 5 items
					break;
			case 3:	//TestCase4
					ManagerNum = 0;	
					LostChance = 0;
					ReturnChance = 0;
					OriginItemAmount = 1000;
					MinBoughtEach = 2;			//each customer buy exactly 2 item
					MaxBoughtEach = 1;
					break;
			case 4:	//TestCase5
					LostChance = 0;
					ReturnChance = 0;
					MinBoughtEach = 1;
					MaxBoughtEach = 1;
					OriginItemAmount = 1000;
					break;
			case 5:	//TestCase6
					LostChance = 0;
					ReturnChance = 0;
					OriginItemAmount = 10000;
					MinBoughtEach = 5;			//each customer buy exactly 5 items
					MaxBoughtEach = 1;
					PriceFactor = 1;			//Price of each item has to be 1.0
					MinPrice = 0.9;
					break;
			case 6:	//TestCase7
					ManagerNum = 0;
					LostChance = 100;
					ReturnChance = 0;
					OriginItemAmount = 10;
					MinBoughtEach = 1;
					MaxBoughtEach = 1;
					CustomerBusyWaiting = true;
					break;
			case 7:	//TestCase8
					ManagerNum = 0;
					OriginItemAmount = 100;
					break;
			case 8: //MinimalRequirement
					break;
			default:
					break;
		}
	}

	//------------------------------
	//           INITIALIZE
	//------------------------------
	
	//Initialization of varibles declared
	OpLock1 = new Lock("OperationLock1");		
	OpLock2 = new Lock("OperationLock2");
	OpLock3 = new Lock("OperationLock3");
	OpLock4 = new Lock("OperationLock4");
	OpLock5 = new Lock("OperationLock5");
	
	StartLine = new Condition("StartLine");
	
	ClerkOnBreak = new Condition("ClerkBreak");
	StockBoyOnBreak = new Condition("StockBoyBreak");

	CheckQueue = new Lock("CheckQueueLock");
	QueueLength = new int[CRNum];
	Queue = new Condition*[CRNum];
	ClerkOnWork = new bool[ClerkNum];
	BornLazy = new bool[ClerkNum];


	TableLock = new Lock*[CRNum];
	Table = new Condition*[CRNum];
	TableArea = new int[CRNum];
	CashArea = new double[CRNum];

	ScreenLock = new Lock*[CRNum];
	Screen = new Condition*[CRNum];
	data = new double[CRNum];
	MoneyLacked = new double[CRNum];
	LackMoney = new Condition*[CRNum];


	MoneyCollected = new double[CRNum];
	TotalMoneyCollected = new double[CRNum];
	
	StockBoyStatus = new int[StockBoyNum];	
	StockRoomLock = new Lock("StockRoomLock");
	StockRoomCV = new Condition("StockRoomCV");

	AisleLock = new Lock*[AisleNum];
	AisleHelpLineLength = new int[AisleNum];	
	
	ServiceStateLock = new Lock*[StockBoyNum];
	ServiceStateCV = new Condition*[StockBoyNum];
	
	Booklet = new int[StockBoyNum];
	DidSomething = new bool[StockBoyNum];

	ServiceButtonLock = new Lock("ServiceButtonLock");
	StockBoyStatusLock = new Lock("StockBoyStatusLock");
	
	AisleHelpLock = new Lock*[AisleNum];
	AisleHelpCV = new Condition*[AisleNum];
	AisleNeedRestock= new bool[AisleNum];
	
	ClerkCallLock=new Lock("ClerkCallLock");

	WaitForRestockCV = new Condition*[ItemNum];				//there is a waiting condition for each item. 

	//Initialization of array varibles declared
	for(int i=0;i<CRNum;i++)
	{
		char* name;
		
		name = new char[8];
		sprintf(name,"Queue%02d",i);
		Queue[i] = new Condition(name);

		QueueLength[i] = 0;									//origin length of each line is 0
		ClerkOnWork[i] = true;								//Erery clerk is assumed to be on work at beginning
		BornLazy[i] = false;								//he won't go to rest directly

		name = new char[12];
		sprintf(name,"TableLock%02d",i);
		TableLock[i] = new Lock(name);

		name = new char[8];
		sprintf(name,"Table%02d",i);
		Table[i] = new Condition(name);
		
		TableArea[i]=-1;									//default value
		CashArea[i]=0.0;

		name = new char[13];
		sprintf(name,"ScreenLock%02d",i);
		ScreenLock[i] = new Lock(name);

		name = new char[9];
		sprintf(name,"Screen%02d",i);
		Screen[i] = new Condition(name);
		
		data[i] = -1.0;										//-1 is used to denote initial state for cash register

		MoneyCollected[i] = 0.0;							//originally each cash register has no profit
		TotalMoneyCollected[i] = 0.0;

		MoneyLacked[i] = -1.0;								//MoneyLacked < 0 means no money lacked
		
		name = new char[7];
		sprintf(name,"Lack%02d",i);
		LackMoney[i] = new Condition(name);
		
	}

	for(int i=0;i<StockBoyNum;i++)
	{
		char * name;

		name = new char[19];
		sprintf(name,"ServiceStateLock%02d",i);
		ServiceStateLock[i] = new Lock(name);

		name = new char[15];
		sprintf(name,"ServiceState%02d",i);
		ServiceStateCV[i] = new Condition(name);

		Booklet[i] = -1;									//Default value
		StockBoyStatus[i] = -1;								//StockBoyStatus == -1 means he is out of any aisle
	}

	for (int i=0;i<AisleNum;i++)
	{
		char* name;
		name=new char[17];
		sprintf(name,"AisleHelpLock%03d",i);
		AisleHelpLock[i]=new Lock(name);

		name=new char[15];
		sprintf(name,"AisleHelpCV%03d",i);
		AisleHelpCV[i]=new Condition(name);

		name=new char[12];
		sprintf(name,"AisleLock%02d",i);
		AisleLock[i]=new Lock(name);

		AisleHelpLineLength[i]=0;							//originally no customer is waiting for help in any aisle
		AisleNeedRestock[i] = false;						//no aisle need to be restocked at very beginning
	}
	

	//Initialize Items	
	Prices = new double[ItemNum];
	ItemAmount = new int[ItemNum];
	ItemRestockPrediction = new int[ItemNum];

	for(int i=0;i<ItemNum;i++)
	{
		Prices[i]=MinPrice+(1+GenRandom(PriceFactor))/10.0;				//generate price
		ItemAmount[i]=OriginItemAmount;					//Default amount of each item is 3
		ItemRestockPrediction[i]=0;						//Item to be restocked is 0	

		char * name;
		name=new char[20];
		sprintf(name,"WaitForRestockCV%03d",i);
		WaitForRestockCV[i]=new Condition(name);
	}


	//---------------------------
	//      CONFIG   Phase2
	//---------------------------

	// In phase2, initialized varibles will be configed to create specific scenario

	switch(TestCaseId)
	{
		case 0:	//TestCase1
				QueueLength[0]=2;						//Set length of paying line 0,1,2 to be 2,4,6
				QueueLength[1]=4;
				QueueLength[2]=6;
				break;
		case 1:	//TestCase2
				break;
		case 2:	//TestCase3
				break;
		case 3:	//TestCase4
				break;
		case 4:	//TestCase5
				BornLazy[3]=true;						//let clerk 3 and 4 rest at the very beginning
				BornLazy[4]=true;
				ClerkOnWork[3]=false;
				ClerkOnWork[4]=false;
				QueueLength[0]=10;						//Set length of paying line 0,1,2 to be 2,4,6
				QueueLength[1]=10;
				QueueLength[2]=10;
				QueueLength[3]=50;
				QueueLength[4]=50;
				//ManagerTrackLine = false;				//we are testing if clerk can call manager to add clerk
				break;
		case 5:	//TestCase6
				break;
		case 6:	//TestCase7
				BornLazy[0]=true;						//let clerk 0 rest
				break;
		case 7:	//TestCase8
				ItemAmount[6]=0;						//set amount of item 6 to be 0
				break;
		case 8: case 9:	//MinimalRequirement & UserConfig, simply avoid config phase2
				break;
		default://Invalid test case ID
				printf("Invalid TestCase Id, program terminate!!");
				return;
	}
	
	//build Threads

	//CashRegisters
	for(int i=0;i<CRNum;i++)
	{
		char* name = new char[7];					// 6 chars of name + 1 char of \0
		sprintf(name,"CR_%03d",i);
		Thread * thread = new Thread(name);
		thread->Fork(CashRegisterBehavior,i);		// Fork a new thread on CashRegister's Behavior, that makes him a CR
		currentThread->Yield();						// EVERY TIME A NEW THREAD IS CREATED, YIELD TO IT!! To make sure they are waiting on start line;
	}
	
	//StockBoys
	for(int i=0;i<StockBoyNum;i++)
	{
		char* name = new char[7];					// 6 chars of name + 1 char of \0
		sprintf(name,"SB_%03d",i);
		Thread * thread = new Thread(name);
		thread->Fork(StockBoyBehavior,i);			// Fork a new thread on StockBoy's Behavior, that makes him a StockBoy
		currentThread->Yield();						// EVERY TIME A NEW THREAD IS CREATED, YIELD TO IT!! To make sure they are waiting on start line;
	}

	//Manager
	for(int i=0;i<ManagerNum;i++)
	{
		char* name=new char[8];						// 7 chars of name + 1 char of \0
		sprintf(name,"Manager");
		Thread * thread=new Thread(name);
		thread->Fork(ManagerBehavior,0);
		currentThread->Yield();
	}

	//Customers	
	for(int i=0;i<CustomerNum;i++)
	{
		char * name = new char[8];					// 7 chars of name + 1 char of \0
		sprintf(name,"Cus_%03d",i);
		Thread * thread = new Thread(name);
		thread->Fork(CustomerBehavior,i);			// Fork a new thread on Customer's Behavior, that makes him a customer
		currentThread->Yield();						// EVERY TIME A NEW THREAD IS CREATED, YIELD TO IT!! To make sure they are waiting on start line;
	}

	//Clerks
	for(int i=0;i<ClerkNum;i++)
	{
		char * name = new char[10];					// 9 chars of name + 1 char of \0
		sprintf(name,"Clerk_%03d",i);
		Thread * thread = new Thread(name);
		thread->Fork(ClerkBehavior,i);				// Fork a new thread on Clerk's Behavior, that makes him a clerk
		currentThread->Yield();						// EVERY TIME A NEW THREAD IS CREATED, YIELD TO IT!! To make sure they are waiting on start line;
	}


	currentThread->Yield();
	printf("================ Program Start =============\n");	//Simulation Start

	printf("Number of Clerks = [%d]\n",ClerkNum);				//print as sample out put
	printf("Number of StockBoys = [%d]\n",StockBoyNum);
	printf("Number of CashRegisters = [%d]\n",CRNum);
	printf("Number of Customers = [%d]\n",CustomerNum);
	printf("Number of Managers = [%d]\n",ManagerNum);
	printf("Number of Aisles = [%d]\n",AisleNum);
	printf("	Items:\n");
	printf("		Number - Price\n");
	for(int i=0;i<ItemNum;i++)
		printf("		[%d] - $[%0.1f]\n",i,Prices[i]);


	
	//simulation start
	OpLock1->Acquire();	
	StartLine->Broadcast(OpLock1);					//simulation started, let created thread to start running
													//Professor Crowley says it won't affect the result
	OpLock1->Release();
}

void
WaitForStart()		//Wait here for the signal to start
{
	OpLock1->Acquire();	
	StartLine->Wait(OpLock1);						//wait for signal to run
	OpLock1->Release();
}

int
GetAisleByItem(int item)
{
	return (item/2);								//The method to find aisle number by item number
}
//=======================================================

//-------------------Customer Minor----------------------
//	Minor Behaviors of Customer
//	Lots of synchronization involved
//-------------------------------------------------------
void
PressServiceButton()								//Press the service button
{
	ServiceButtonLock->Acquire();
	ServiceButtonOn=true;
	ServiceButtonLock->Release();
}


int
AskStockBoyForItem(int item,int id)					//When customer ask stock boy for position of item
{
	int helpAisle = -1;
	int myStockBoy = -1;
	int myAisle = -1;

	//find an aisle number depending on the stockboy's Status.
	//We will enter aisles one by one, and see if there is a StockBoy whose Status == aisleID; If yes, we know there is one workging in current aisle ,and wait here
	while(true)
	{

		for(int i=0; i<AisleNum; i++)				//Enter	aisles one by one			
		{
			AisleHelpLock[i]->Acquire();			//Once in an aisle, acquire its aisle help lock
			for(int j=0; j<StockBoyNum; j++)
			{
				// between the steps a customer find a stockboy, and increase the aisleHelpLine, 
				// the stockboy has no chance to run 
				StockBoyStatusLock -> Acquire();
				if( (StockBoyStatus[j] != -1) && ( StockBoyStatus[j] % AisleNum == i) )//if there is a stock boy in current aisle, remember this aisle
				{
					StockBoyStatusLock -> Release();
					helpAisle = i;
					break;
				}
				StockBoyStatusLock -> Release();
			}
			if(helpAisle != -1)						//helpAisle!=-1 means we found a stockboy, break without releasing AisleHelpLock
				break;
			AisleHelpLock[i] -> Release();			//Otherwise, release lock, look another aisle
		}
			
		if(helpAisle == -1)							//looked into all aisles and found no stockboy
		{
			if(CustomerBusyWaiting)					//This trick is only used in scenario that without manager.
				continue;

			printf("Customer [%d] looked in all aisle for StockBoy. He is now requesting help by pressing service button.\n", id);
			PressServiceButton();					//press service button
			WaitForStart();							//wait on start line for calling from manager when stockboy is ready
			continue;								//when waken uo by manager, go back to head of this function, re do task
		}
		else										//We found a stock boy in aisle
		{
			//printf("===Customer [%d] find a stockboy in aisle [%d], get in line\n", id, helpAisle);
		
			AisleHelpLineLength[helpAisle]++;		//Change help line length
			AisleHelpCV[helpAisle] -> Wait(AisleHelpLock[helpAisle]);//wait in help CV
			AisleHelpLock[helpAisle] -> Release();	//After wake up, release help lock: help line length should have been decremented by stock boy

			// find which stockboy is ready for helping me

			//printf("===Customer [%d] is told one stockboy is waiting for him, he is searching status [%d] in aisle [%d]\n", id, helpAisle + AisleNum,helpAisle);
		
			StockBoyStatusLock -> Acquire();
			for(int i=0; i<StockBoyNum; i++)		//look which stockboy said to serve me 
			{
				//printf("StockBoy #%d Status: %d, I am searching for status %d\n",i,StockBoyStatus[i],helpAisle+AisleNum);
				if(StockBoyStatus[i] == helpAisle + AisleNum)//A stock boy ready to serve will set his status to [ AisleNumber + AisleNum  ]
				{
					StockBoyStatus[i] = helpAisle;	//Reset this stockboy's Service status, so that other customer won't ask him at the same time
					myStockBoy = i;
					break;
				}
			}
			StockBoyStatusLock -> Release();
			
			printf("Customer [%d] is asking for assistance from StockBoy [%d]\n", id, myStockBoy);
		
			//Start interaction with stockboy
			ServiceStateLock[myStockBoy] -> Acquire();
		
			Booklet[myStockBoy] = id;				//First, tell stockboy my id
			
			ServiceStateCV[myStockBoy] -> Signal(ServiceStateLock[myStockBoy]);
			ServiceStateCV[myStockBoy] -> Wait(ServiceStateLock[myStockBoy]);
			
			//printf("=== %s ask a question: where is item%d\n", name, item);
			Booklet[myStockBoy] = item;				//Then, tell stockboy the item I want 
		
			ServiceStateCV[myStockBoy] -> Signal(ServiceStateLock[myStockBoy]);
			ServiceStateCV[myStockBoy] -> Wait(ServiceStateLock[myStockBoy]);
			
			myAisle = Booklet[myStockBoy];			//Then, get answer from stockboy
			
			ServiceStateCV[myStockBoy] -> Signal(ServiceStateLock[myStockBoy]);	//Tell stockboy I am satisfied
			
			printf("Customer [%d] got aisle [%d] from StockBoy [%d]\n" ,id, myAisle, myStockBoy);
		
			ServiceStateLock[myStockBoy] -> Release();
			//Interaction with stockboy end

			return myAisle;
		}
	}
}

void
GetItem(int item)
{
	int aisle = GetAisleByItem(item);				//Fetch the aisle number

	AisleLock[aisle]->Acquire();					//Enter Aisle

	while(true)
	{
		if(ItemAmount[item]>0)						//If Item is not empty, get it and leave
		{
			ItemAmount[item]--;
			break;
		}
		else										//Else, wait for it to be restocked
		{
			//Item Not Enough, have to wait
			WaitForRestockCV[item]->Wait(AisleLock[aisle]);
			continue;								//When told item is restocked, redo GetItem();
		}
	}

	AisleNeedRestock[aisle]=true;					//Since I just fetched that item, lit Aisle light saying this aisle nees restock
	AisleLock[aisle]->Release();
}

void 
CallManagerForClerk()								//If there is no clerk available, call manager
{
	ClerkCallLock->Acquire();						
	ClerkCall = true;
	ClerkCallLock->Release();
}

int
FindShortestQueueAndWait(int id)					//find the shortest queue, and wait there
{
	int people=RAND_MAX;							//RAND_MAX is the biggest integer defined
	int number = -1;
	
	while(true)
	{
		CheckQueue->Acquire();
	
		for(int i=0;i<CRNum;i++)					//loop all lines
		{
			if(!ClerkOnWork[i])						//If that line is closed, check next
				continue;

			if(QueueLength[i]<people)				//If Line length is shorter, remember his number and line length
			{
				people=QueueLength[i];
				number=i;
			}
		}

		if(number == -1)							//No Line is picked, means All line is closed, shoule call manager
		{
			//printf("Customer %d: can't find any clerk, call manager!!!\n",id);
			CallManagerForClerk();					//Call manager
			CheckQueue->Release();
			WaitForStart();							//wait in start line, the manager will call him
			continue;								//Redo Find Shortest after wakeup
		}

		printf("Customer [%d] chose Clerk [%d] with line length of [%d]\n",id,number, people);//When called by clerk, start to show bought item

		QueueLength[number]++;						//Add self to that line
		Queue[number]->Wait(CheckQueue);			//Wait
		QueueLength[number]--;						//When awake from wait, leave the line to stand in front of table

		CheckQueue->Release();
		return number;
	}
}

void
ShowItem(int item,int queueNumber)					//show item to clerk on queueNumber
{
	TableArea[queueNumber]=item;
	Table[queueNumber]->Signal(TableLock[queueNumber]);
	Table[queueNumber]->Wait(TableLock[queueNumber]);
}

double
TellClerkToCountAndPay(int queueNumber,int id, bool ret)//Tell clerk transaction over
{
	ShowItem(-1,queueNumber);						//According to protocol, show clerk -1 means transaction is over
	double total = CashArea[queueNumber];			//Get the total cost returned from clerk
	
	Table[queueNumber]->Signal(TableLock[queueNumber]);	//Tell clerk I acknowladged the total cost
	
	if(ret)
		printf("Customer [%d] receives [%0.1f] from Clerk [%d] and is now waiting for receipt.\n", id, total, queueNumber);
	else
		printf("Customer [%d] pays [%0.1f] to Clerk [%d] and is now waiting for receipt.\n", id, total, queueNumber);

	Table[queueNumber]->Wait(TableLock[queueNumber]);	//wait for clerk to do something
	
	return total;
}

void
Leave(int queueNumber)									//Cuatomer leave the store
{
	Table[queueNumber]->Signal(TableLock[queueNumber]);	//Tell clerk I left
	
	OpLock4->Acquire();									//Add leaving customer statistics. Manager will rely on this to close sstore
	CustomerLeaving++;
	//printf("Total Finished Customer : %d\n", CustomerLeaving);
	OpLock4->Release();
}

//---------------------Customer Major--------------------
//Customer Behavior
//	the main Logic of a Customer
//-------------------------------------------------------
void
CustomerBehavior(int id)
{
	//NEEDN'T WORRY LOCAL VARIBLES, THEY ARE STORED IN STACK, AND WON'T BE MANIPULATED BE OTHER THREADS
	bool retCustomer = false;							//Am I a return customer?
	char* name = currentThread->getName();
	WaitForStart();

	int tmp = GenRandom(100);							//Roll the dice to decide if I am a return customer
	if(tmp<ReturnChance)
		retCustomer = true;

	int TotalNum = MinBoughtEach+GenRandom(MaxBoughtEach);//Randomly generate total Number of items to buy. Assuming buy no more than MaxBoughtEach
	
	if(retCustomer)										//Start purchasing
		printf("Customer [%d] needs to return [%d] no.of item.\n", id, TotalNum);
	else
		printf("Customer [%d] wants to buy [%d] no.of items.\n",id,TotalNum);	

	int * Items = new int[TotalNum];					//Generate Item List 
	for(int i=0;i<TotalNum;i++)				
	{
		Items[i]=GenRandom(ItemNum);					//Randomly generate item id
		
		if(retCustomer)									//Return customer don't need to fetch items.
			continue;

		tmp = GenRandom(100);							//Roll the dice to decide if customer fail to find the item
		if(tmp<LostChance)								//If failed, customer have to look for a stockboy for help
		{
			printf("Customer [%d] is not able to find item [%d] and is searching for StockBoy.\n",id,Items[i]);
			AskStockBoyForItem(Items[i],id);			//Ask StockBoy for help
		}

		GetItem(Items[i]);								//Take the item;	
		//printf("Customer %s: Bought item %d\n",name,Items[i]);
	}
	
	//printf("Customer %s: Finished purchasing, trying to find a paying queue\n",name);//finish purchasing,trying to find a queue

	int QueueNumber = FindShortestQueueAndWait(id);		//find the shortest queue, and wait there

	TableLock[QueueNumber]->Acquire();					//Make Critical Section
	
	ShowItem(id,QueueNumber);							//Tell Clerk my name

	ShowItem((retCustomer?1:0),QueueNumber);			//Tell Clerk my purpose: 1,return item; 0,buy item;

	for(int i=0;i<TotalNum;i++)							//show items to clerk, one by one
	{
		printf("Customer [%d] gives item [%d] to Clerk [%d].\n", id, Items[i],QueueNumber);
		ShowItem(Items[i],QueueNumber);			
	}
	
	printf("Customer [%d] tells Clerk [%d], I have given you all my [%d] items.\n", id, QueueNumber, TotalNum);

	TellClerkToCountAndPay(QueueNumber, id, retCustomer);//tell clerk to count total, and pay for them,then wait for receipt

	Leave(QueueNumber);									//take recipet and leave store

	printf("Customer [%d] got receipt from Clerk [%d] and is now leaving.\n",id, QueueNumber);

	TableLock[QueueNumber]->Release();					//Critical Section End
}

//---------------------Clerk Minor-----------------------
//	Minor Behaviors of Clerk
//	Lots of synchronization involved
//-------------------------------------------------------

int
CheckWaitingQueue(int id)								//Check length of paying line
{
	int length = QueueLength[id];
	return length;
}

void
CallManager(int id)										//Clerk will cal manager if there are too many customer in line
{
	printf("Clerk [%d] sees more than 4 people in line and calls manager.\n",id);
	ClerkCallLock->Acquire();
	ClerkCall=true;
	ClerkCallId = id;
	ClerkCallLock->Release();
}

void
ClerkRest(int id)										//Clerk go to rest, assumes ClerkOnWork has been marked false
{
	printf("Clerk [%d] is leaving Cash Register [%d] and going on break.\n",id,id);
	
	OpLock3->Acquire();
	ClerkOnBreak->Wait(OpLock3);						//Wait on clerk break condition
	OpLock3->Release();
	
	printf("Clerk [%d] was called by Manager to work.\n",id);	//Waken by manager to work

	CheckQueue->Acquire();
	ClerkOnWork[id]=true;								//Reset ClerkOnWork to true
	CheckQueue->Release();

	for(int i=0;i<20;i++)								//Wait for some time, let customer wait in line
		currentThread->Yield();
}

void
GreetOneWaiter(int id)									//Tell one customer in line to hand off items
{
	Queue[id]->Signal(CheckQueue);
}

int 
checkTable(int id)										//Check what has been put in table by customer
{
	Table[id]->Signal(TableLock[id]);
	Table[id]->Wait(TableLock[id]);
	return TableArea[id];
}

void
TypeInCashier(int id,int item)							//Clerk type information in cash register
{
	data[id] = (double) item;
	Screen[id]->Signal(ScreenLock[id]);
	Screen[id]->Wait(ScreenLock[id]);					//Wait for cash register's reflection
}

double
ReadScreen(int id)										//Type in all item scanned, and read screen for total cost
{
	TypeInCashier(id,-1);								//According to protocol, -1 tells cash register transcation over and let it count total
	double total = data[id];							//Read total
	return total;
}

void
ProvideReceipt(int id)
{
	Table[id]->Signal(TableLock[id]);					//Provide receipt
	Table[id]->Wait(TableLock[id]);						//Wait for customer to take receipt and leave
}


//---------------------Clerk Major-----------------------
//Clerk Behavior
//	the main Logic of a Clerk
//-------------------------------------------------------

//Assumption:	Each Clerk works on CashRegister corresponding to his number
void
ClerkBehavior(int id)
{
	char * name = currentThread->getName();
	WaitForStart();

	if(BornLazy[id])									//Used by test case, some clerk go to rest at very beginning
	{
		CheckQueue->Acquire();
		ClerkOnWork[id]=false;
		CheckQueue->Release();
		ClerkRest(id);
	}

	for(int i=0;i<5;i++)								//When just created, yield some time to make sure some customer finish shopping
		currentThread->Yield();

	//printf("Clerk %s: Ready to work\n",name);

	while(ProgramRun)									//As long as program is running
	{
		for(int i=0;i<5;i++)
		{
			currentThread->Yield();
		}
		
		
		CheckQueue->Acquire();
		int people = CheckWaitingQueue(id);				//Check line length
		
		//printf("Clerk %s: %2d people are waiting in line\n",name,people);
		
		if(people>=4)									//If more than 4 people waiting in line, call manager
			CallManager(id);
		else if(people==0)								//If no people waiting, go to rest
		{
			ClerkOnWork[id]=false;						//Mark work status to be false
			CheckQueue->Release();	
			ClerkRest(id);								//go to rest
			continue;									//when waken by manager, start a new work cycle
		}
		
		//printf("Clerk %s: Tell one customer in line to take off items\n",name);
		
		GreetOneWaiter(id);								//Tell one customer to show item, and grabing Table Lock
		
		TableLock[id]->Acquire();						//Acquire Table Lock first to avoid lost signal from customer
		
		CheckQueue->Release();

		Table[id]->Wait(TableLock[id]);					//wait for customer to come
		
		int cusId = TableArea[id];						//check customer id placed on table area by customer

		ScreenLock[id]->Acquire();		

		TypeInCashier(id,cusId);						//Type customer id in cash register

		bool retCustomer = checkTable(id);				//check if the customer is a return customer
	
		//printf("!!!!! Clerk [%d] knows Customer [%d] is [%s] a return customer!!!!\n",id, cusId, retCustomer?"":"NOT");
		
		TypeInCashier(id,retCustomer);					//Type customer purpose in cash register

		int item = checkTable(id);						//start to scan customer item

		while(item!=-1)									//As long as item!= -1, keep taking new items and type in cash register
		{
			printf("Clerk [%d] got item [%d] from Customer [%d]\n", id, item, cusId);
			printf("Clerk [%d] gave item [%d] to Cash Register [%d] for scanning.\n", id, item, id);
			TypeInCashier(id,item);						//type item into cashier
			item = checkTable(id);						//check another item	
		}
		
		//printf("Clerk %s: Command computer to count total\n",name);
		
		double total = ReadScreen(id);					//Tell machine to count and read Cashier Screen for total
		
		printf("Clerk [%d] got total cost $[%0.1f] from Cash Register [%d]\n", id, total, id);
		
		printf("Clerk [%d] tells Customer [%d] total cost is $[%0.1f].\n",id,cusId,total);	//Tell Customer amount
	
		if(retCustomer)									//If this is a return customer, we have to provide cash along with total value
		{	
			Screen[id]->Signal(ScreenLock[id]);			//tell cash register to prepare cash
			Screen[id]->Wait(ScreenLock[id]);			//wait for cash to be prepared together with receipt
			CashArea[id] = total;						//put money on cash area
			printf("Clerk [%d] got money $[%0.1f] from Cash Register [%d].\n", id, total, id);
			Table[id]->Signal(TableLock[id]);			//tell customer to pick cash
			printf("Clerk [%d] gave the money $[%0.1f] to Customer [%d].\n", id, total, cusId);
			Table[id]->Wait(TableLock[id]);				//Now customer has been paid
		}
		else											//if it is a normal customer, collect cash from him 
		{
			CashArea[id] = total;						//show total cost to customer
			Table[id]->Signal(TableLock[id]);			//Tell customer to pay
			Table[id]->Wait(TableLock[id]);				//Now customer has paid
			printf("Clerk [%d] got money $[%0.1f] from Customer [%d].\n", id, total, cusId);
			Screen[id]->Signal(ScreenLock[id]);			//tell chase register money has been collected
			printf("Clerk [%d] gave the money $[%0.1f] to Cash Register [%d].\n", id, total, id);
			Screen[id]->Wait(ScreenLock[id]);			//wait for machine to take in money
		}

		Screen[id]->Signal(ScreenLock[id]);				//tell cash register to print receipt
		Screen[id]->Wait(ScreenLock[id]);				//wait for receipt
		printf("Clerk [%d] got receipt from Cash Register [%d].\n", id, id);
		ScreenLock[id]->Release();
		printf("Clerk [%d] gave the receipt to Customer [%d] and tells him to leave.\n", id, cusId);
		ProvideReceipt(id);								//provide receipt to customer, and wait for him to leave
		TableLock[id]->Release();
	}
}

//---------------------CashReg Minor---------------------
//	Minor Behaviors of CashRegister
//	Lots of synchronization involved
//  by OceanMaster
//-------------------------------------------------------

int
CheckInput(int id)										//check input from clerk
{
	Screen[id]->Signal(ScreenLock[id]);
	Screen[id]->Wait(ScreenLock[id]);
	int i = (int)data[id];
	return i;
}

void
DisplayTotal(int id, double total)						//Display total cost to clerk
{
	data[id]=total;
	Screen[id]->Signal(ScreenLock[id]);
	Screen[id]->Wait(ScreenLock[id]);					
}

//---------------------CashReg Major---------------------
//CashRegister Behavior
//	the main Logic of a CashRegister
//  by OceanMaster
//-------------------------------------------------------
void 
CashRegisterBehavior(int id)
{
	char * name = currentThread->getName();
	WaitForStart();
	
	ScreenLock[id]->Acquire();							//The Lock controls interaction with cash register
	
	//printf("CashMachine %s: Trun On\n",name);

	while(ProgramRun)									//As long as programming is running..
	{
		//printf("CashMachine %s: Ready for input\n",name);
	
		double total = 0.0;								//Assuming a new transcation starts
		int cusId = CheckInput(id);						//Get customer id
		bool retCustomer = CheckInput(id);				//Get customer purpose : return customer or not

		int item = CheckInput(id);						//Scan a new item
		int amount = 0;									//Store total amount

		while(item!=-1)									//If it isn't -1; (Item is -1 means all item is scanned, should display Total amount)
		{
			amount++;									//count total amount of items
			total += Prices[item];						//Add item's price to total cost
			printf("Cash Register [%d] got item [%d] from clerk [%d] to scan.\n", id, item, id);
			item = CheckInput(id);						//Scan a new item
		}
		printf("Cash Register [%d] has scanned all [%d] items for Customer [%d]\n", id, amount, id);
		printf("Cash Register [%d] gave total cost $[%0.1f] for Customer [%d] to Clerk[%d] for [%d] items.\n", id, total, cusId, id, amount);
		
		DisplayTotal(id,total);							//Display total Amount to screen
		
		if(retCustomer)									//We have to prepare cash for return customer
		{
			if((MoneyCollected[id]-total)>=0)			//If MoneyCollected enough to pay customer
			{
				MoneyCollected[id]-=total;				//Pay it directly
			}
			else										//Otherwise, we have to count on manager to solve the problem
			{
				double lacked = total - MoneyCollected[id];	//Count how much I lack
				MoneyCollected[id] = 0;						//Empty Money Collected to pay customer
				printf("Cash Register [%d] informed the Manager that he needs $[%0.1f].\n",id, lacked);
				MoneyLacked[id] = lacked;					//store amount of money lacked
				LackMoney[id]->Wait(ScreenLock[id]);		//Wait for manager to come
				printf("Cash Register [%d] received $[%0.1f] from the Manager.\n", id, lacked);
			}
		
			data[id]=total;								//display total
			printf("Cash Register [%d] gave the money to Clerk [%d].\n", id, id);
			Screen[id]->Signal(ScreenLock[id]);			//provided cash
			Screen[id]->Wait(ScreenLock[id]);			//wait for clerk to transmit money
		}
		else											//If it is normal customer, now cash should have been put in front of machine
		{
			MoneyCollected[id]+=total;					//take cash in machine balance
			printf("Cash Register [%d] got the money from Clerk [%d].\n", id, id);
			Screen[id]->Signal(ScreenLock[id]);			//tell clerk money has been saved
			Screen[id]->Wait(ScreenLock[id]);			//wait for command to provide receipt
		}
		
		printf("Cash Register [%d] gave receipt to Clerk[%d] for Customer [%d].\n", id, id, cusId);
		Screen[id]->Signal(ScreenLock[id]);				//provided receipt
		printf("Cash Register [%d] total sale is $[%0.1f].\n", id, MoneyCollected[id]);
	}
	ScreenLock[id]->Release();
}


//---------------------StockBoy Minor--------------------
//	Minor Behaviors of StockBoy
//	Lots of synchronization involved
//	by Kuai Yu
//-------------------------------------------------------
void
RetrieveStockItem(int item, int id)						//Retrieve item form stock room
{
	//printf("===StockBoy [%d] want to retrieve item [%d]\n",id,item);

	OpLock5->Acquire();
	while(true)
	{
		if(StockBoyInRoom!=-1)							//If stockroom is currently occupied
		{
			printf("StockBoy [%d] is waiting for StockBoy [%d] to leave the stock room.\n",id,StockBoyInRoom);
			StockRoomCV->Wait(OpLock5);					//wait for stock boy in room to leave
			continue;									//Re do check stock room
		}
		StockBoyInRoom = id;							//If not occupied, register self
		OpLock5->Release();
		break;
	}

	StockRoomLock->Acquire();							//Enter stock room
	
	printf("StockBoy [%d] is in stock room.\n", id);

	for(int i=0;i<10;i++)								//It takes time to pick item
		currentThread->Yield();

	printf("StockBoy [%d] retrieve one new item [%d] from stock room.\n",id,item);
	printf("StockBoy [%d] leaves stock room.\n", id);

	StockRoomLock->Release();							//leave stock room

	OpLock5->Acquire();
	StockBoyInRoom = -1;								//mark nobody is in stockroom
	StockRoomCV->Signal(OpLock5);						//tell one stockboy to retry entering stockroom
	OpLock5->Release();
}

void 
ServeCustomerAndLeaveAisle(int StockBoyId, int MyAisle)	//Stock boy serve suctomer and leave aisle after that
{
	//printf("===StockBoy [%d] want to serve customer in aisle [%d]\n",StockBoyId,MyAisle);
	
	if(MyAisle<0)										//if stockboy is not in any aisle, won't serve customer
		return;

	char * name = currentThread->getName();

	//printf("=== %s is yielding...\n", name);

	for (int i=0;i<5;i++)								//it takes some time to walk to the end of aisle
	{
		currentThread->Yield();
	}
	
	AisleHelpLock[MyAisle]->Acquire();					//Acquire help lock

	while(AisleHelpLineLength[MyAisle]>0)				//while there is still customer waiting for service
	{
		DidSomething[StockBoyId] = true;				//I did something when help customer

		//printf("===StockBoy [%d] find [%d] customers waiting in aisle %d\n", StockBoyId, AisleHelpLineLength[MyAisle],MyAisle);

		AisleHelpCV[MyAisle]->Signal(AisleHelpLock[MyAisle]);	//Tell one customer to ask question

		AisleHelpLineLength[MyAisle]--;					//decrement helpline length

		StockBoyStatusLock->Acquire();					//Acquire status lock before release helplock, make sure customer has no chance to run before i am ready

		AisleHelpLock[MyAisle]->Release();

		//printf("===StockBoy [%d] is waiting to help one customer in aisle %d\n", StockBoyId, MyAisle);
	
		StockBoyStatus[StockBoyId] = MyAisle + AisleNum;//mark my status as [Aisle +AisleNum], that is the status for ready to serve in aisle;

		//printf("===StockBoy [%d] set his Status: %d\n", StockBoyId, StockBoyStatus[StockBoyId]);
		
		ServiceStateLock[StockBoyId]->Acquire();		//Acquire service state lock, entering service section

		StockBoyStatusLock->Release();
		
		ServiceStateCV[StockBoyId]->Wait(ServiceStateLock[StockBoyId]);// wait for customer to ask question
		
		int cusId=Booklet[StockBoyId];					//get customer id

		ServiceStateCV[StockBoyId]->Signal(ServiceStateLock[StockBoyId]);// tell customer to go on
		ServiceStateCV[StockBoyId]->Wait(ServiceStateLock[StockBoyId]);
		
		printf("StockBoy [%d] is approached by Customer [%d] for assistance.\n", StockBoyId, cusId);

		int item=Booklet[StockBoyId];					//get customer's question

		//printf("=== %s get a question from customer: where is item%d\n", name, item);
		
		int aisle = GetAisleByItem(item);				//find the answer

		Booklet[StockBoyId]=aisle;						//put answer on booklet
		
		printf("StockBoy [%d] gave aisle [%d] to Customer [%d] for item [%d].\n", StockBoyId, aisle, cusId, item);
		
		ServiceStateCV[StockBoyId]->Signal(ServiceStateLock[StockBoyId]);	//tell customer to read answer

		ServiceStateCV[StockBoyId]->Wait(ServiceStateLock[StockBoyId]);		//wait for customer's thanks

		ServiceStateLock[StockBoyId]->Release();

		AisleHelpLock[MyAisle]->Acquire();
	}
	
	StockBoyStatusLock->Acquire();								//Mark self as out of aisle
	//printf("=== %s leaves aisle%d\n", name, MyAisle);
	StockBoyStatus[StockBoyId]=-1;								
	StockBoyStatusLock->Release();
	
	//printf("===StockBoy [%d] left aisle [%d]\n",StockBoyId,MyAisle);

	AisleHelpLock[MyAisle]->Release();

}

int
ScanAisle(int id)												//Stock boy scans aisles to see if items is lacked
{
	for (int i=0;i<AisleNum;i++)								//loop all aisles
	{
		AisleLock[i]->Acquire();								//Entering aisle
		StockBoyStatusLock->Acquire();
		
		//printf("=== %s is scanning aisle%d\n", currentThread -> getName(), i );
		StockBoyStatus[id]=i;									//Update stock boy status. let customer see him
		StockBoyStatusLock->Release();
		
		for(int j = 0; j<2; j++)								//check items on this aisle
		{
			for(int k=0;k<2;k++)								//it takes time to check item status
				currentThread->Yield();
		
			int index = i*2+j;									//calculate item id
			if ( (ItemAmount[index] + ItemRestockPrediction[index] )<OriginItemAmount)//If Item is lacked, and still have space to restock
			{
				ItemRestockPrediction[index]++;					//Mark item that I will restock one of this item
				AisleLock[i]->Release();
				ServeCustomerAndLeaveAisle(id,i);				//Serve customer and leave aisle
				return index;									//Return item id that i am going to restock
			}
		}
		AisleLock[i]->Release();								//Leave aisle
		ServeCustomerAndLeaveAisle(id,i);						//Serve customer before leave aisle
	}

	return -1;													//If no item need to restock, return -1
}

//Assumption: 
//current thread is holding AisleLock[aisle]
bool
isItemFull(int item)											//Check if item is full
{
	return ((ItemAmount[item]+ItemRestockPrediction[item]) == OriginItemAmount);
}

bool
isAisleFull(int aisle)											//Check if aisle is full
{
	return ( isItemFull(aisle*2) && isItemFull(aisle*2+1) );
}

bool
PutStockItem(int item, int id)									//Put retrieved item on its aisle
{
	bool more = false;						

	int aisle = GetAisleByItem(item);							//calculate aisle number

	StockBoyStatusLock->Acquire();
	StockBoyStatus[id] = aisle;									//Mark self status in that aisle
	StockBoyStatusLock->Release();


	AisleLock[aisle]->Acquire();								//Enter aisle
	
	ItemAmount[item]++;											//Restock item 
	ItemRestockPrediction[item]--;								//Delete the mark I left before go get the item
	WaitForRestockCV[item]->Signal(AisleLock[aisle]);			//wake up one customer waiting for item
	
	printf("StockBoy [%d] is checking if more items are to be re-stocked.\n",id);
	
	if(isAisleFull(aisle))
		AisleNeedRestock[aisle] = false;						//If aisle is full, unset the mark that this aisle need restock
	else if(!isItemFull(item))									//If this item is still lacked, go get another
	{
		//Mark I will tock it again
		printf("StockBoy [%d] goes back to stock room for item [%d].\n",id, item);
		ItemRestockPrediction[item]++;							//Leave a mark I am already trying to restock one item of this type
		more = true;											//I will get more this item
	}
	AisleLock[aisle]->Release();								//Leave Aisle

	ServeCustomerAndLeaveAisle(id,aisle);						//Serve customer and leave aisle
	
	return more;
}

void
StockBoyRest(int id)											//Stock boy go to rest
{
	printf("StockBoy [%d] is going on break.\n",id);
	OpLock2->Acquire();
	StockBoyOnBreak->Wait(OpLock2);
	printf("StockBoy [%d] got call from Manager.\n",id);
	OpLock2->Release();
}
//---------------------StockBoy Major--------------------
//StockBoy Behavior
//	the main Logic of a StockBoy
//	by Kuai Yu
//-------------------------------------------------------
void
StockBoyBehavior(int id)
{
	char * name = currentThread->getName();
	WaitForStart();

	while(ProgramRun)											//As long as program is running
	{
		DidSomething[id] = false;
		
		int item = ScanAisle(id);								//Scan aisles for lacked item
		
		if(item != -1)											//if one item is lacked
		{
			//printf("=== %s found item %d is lacked, go to retrieve item\n", name, item);		

			DidSomething[id] = true;							//mark self did something in his loop
			int aisle = GetAisleByItem(item);
		
			RetrieveStockItem(item,id);							//retrieve one item of this type
			//printf("=== %s is in aisle%d, ready to restock item %d\n", name, aisle, item);
			
			while(PutStockItem(item, id))						//put item on aisle. As long as it is still lacked, get one another and restock
			{
				RetrieveStockItem(item,id);
			}
		}

		if(!DidSomething[id])									//If I did nothing in this loop, go to rest
		{
			//printf("StockBoy === %s go to have a rest\n", name);
			StockBoyRest(id);
		}
	}	
}

//---------------------Manager Minor----------------------
//	Minor Behaviors of Manager
//	Lots of synchronization involved
//	by Momo
//--------------------------------------------------------
void
ManagerIdle()													//Manager do this between tasks
{
	for(int i=0;i<10;i++)
		currentThread->Yield();
}

void 
WakeUpCustomer()												//wake up customers
{
	OpLock1->Acquire();
	StartLine->Broadcast(OpLock1);					
	OpLock1->Release();

}

void 
CollectCash()													//Manager collect cash from register machines
{
	for (int i=0;i<CRNum;i++)
	{
		for(int j=0;j<2;j++)									//It takes some time to collect cash from machine
			currentThread->Yield();

		ScreenLock[i]->Acquire();								//Acquire cash register's lock
		
		double lacked = MoneyLacked[i];							//Read register information
		if(lacked>0)											//if this register is needing money
		{
			MoneyCollected[i]=0-lacked;	//TotalSales -= lacked;	//provide money to this cash reg
			MoneyLacked[i]=-1;									//reset data
			LackMoney[i]->Signal(ScreenLock[i]);				//tell that cash register I have provided money
			printf("Manager gave $[%0.1f] to cash register [%d].\n", lacked, i);
		}
		TotalSales+=MoneyCollected[i];							//Collect money, add to total sales			
		TotalMoneyCollected[i]+=MoneyCollected[i];				//Count total sales of eace cash register
		printf("Cash Register [%d] drawer is emptied by Manager.\n",i);
		printf("Cash Register [%d] total sale until now is $[%0.1f].\n", i, MoneyCollected[i]);	//Professor crowley says it is OK
		printf("Manager emptied Cash Register [%d] drawer.\n",i);
		printf("Manager has total sale of $[%0.1f].\n", TotalSales);
		MoneyCollected[i]=0;									//Empty cash reg balance
		ScreenLock[i]->Release();								//Release lock
	}

	if(GenRandom(100)<50)										//Randomly print out this statement
		printf("-------Total Sale of the entire store until now is $[%0.1f]-------\n", TotalSales);
}
//---------------------Manager Major----------------------
//Manager Behavior
//	the main Logic of the Manager
//by Momo
//--------------------------------------------------------
void
ManagerBehavior(int id)
{
	char * name = currentThread->getName();
	WaitForStart();

	while(true)
	{	
		ManagerIdle();

		ClerkCallLock->Acquire();								//check if there is a call for clerk
		if (ClerkCall)
		{
			if(ClerkCallId!=-1)									//if clerk call id is -1, it is from customer, otherwise, print clerk id
			{
				printf("Manager got a call from Clerk [%d].\n",ClerkCallId);
				ClerkCallId = -1;
			}
			
			OpLock3->Acquire();
			ClerkOnBreak->Signal(OpLock3);						//wake up one clerk
			printf("Manager wakes up Clerk.\n");
			OpLock3->Release();
			WakeUpCustomer();									//wake up customers that may be waiting
			ClerkCall=false;
			ClerkCallId = -1;
		}
		ClerkCallLock->Release();
		
		ManagerIdle();

		for (int j=0;j<AisleNum;j++)							//Check if there is an aisle need restock
		{
			AisleLock[j]->Acquire();
			if (AisleNeedRestock[j])							//If there is
			{
				OpLock2->Acquire();
				StockBoyOnBreak->Broadcast(OpLock2);			//wake up all stockboys
				//printf("Items missed in Aisle %d!!Manager call all the Stockboy to work!!\n",j);
				OpLock2->Release();
				AisleLock[j]->Release();
				break;
			}
			AisleLock[j]->Release();
		}

		ManagerIdle();

		ServiceButtonLock->Acquire();							//check if service button is pressed
		if (ServiceButtonOn)									//if pressed
		{
			//wake up all stock boys that are taking break;
			OpLock2->Acquire();
			StockBoyOnBreak->Broadcast(OpLock2);				//wake up all stockboys
			printf("Manager wakes up StockBoy.\n");
			OpLock2->Release();
			WakeUpCustomer();									//wake up customers that may be waiting
			ServiceButtonOn = false;
		}
		ServiceButtonLock->Release();

		ManagerIdle();

		CollectCash();											//collect cash from each cash register

		ManagerIdle();

		if(ManagerTrackLine)									//Manager keep track of line lengths himself
		{
			CheckQueue->Acquire();
			int i;
			for(i=0;i<CRNum;i++)
				if(QueueLength[i]>0 && (!ClerkOnWork[i]))		//If there is a line on which people is waiting but no clerk work
					break;
			CheckQueue->Release();

			if(i!=CRNum)										//such a line exist
			{													//wake up a clerk
				OpLock3->Acquire();
				ClerkOnBreak->Signal(OpLock3);  
				printf("Manager wakes up Clerk.\n");
				OpLock3->Release();
				WakeUpCustomer();								//wake up customer that may be waiting
				ClerkCall=false;
			}
		}

		OpLock4->Acquire();										//Check if all customers have left
		if (CustomerLeaving!=CustomerNum)
		{	
			OpLock4->Release();
			continue;											//if not ,continue
		}
		OpLock4->Release();
		
		//Exiting Codes!										//Else, close store!

		ProgramRun=false;
		//printf("All customer leaves, program exit!!i\n");
		
		CollectCash();											//Collect cash for last time

		//printf("Total Sales: %0.1f\n",TotalSales);
		for (int i=0;i<CRNum;i++)								//Print Statictics
			printf("Total Sale from Cash Register [%d] is $[%0.1f].\n",i,TotalMoneyCollected[i]);
		
		printf("Total Sale of the entire store is $[%0.1f].\n", TotalSales);

		break;													//Thread end
	}
}


//=======================================================

//Description:
//Generate a random integer that  0=< and < limit
//Assumption:
//Already randomized;
int GenRandom(int limit)
{
	//double num;
	//double num2;
	//num = rand()*1.0;
	//printf("%f\n",num);
	//num = limit*num;
	//printf("%f\n",num);
	//num2 = (double)R_MAX+1.0;
	//printf("%f / %f = %f\n",num,num2,num/num2);
	//num = num /num2;
	//num = num +1;
	//printf("%d\n",(int)num);
	
	int result = (int)(limit*(double)rand()/((double)R_MAX+1.0));
	return result;
}
